package gold.digger;

import gold.vo.TreeNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC95 {


    public Map<Integer, List<TreeNode>> memo = new HashMap<>();

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }

        return generateTreesRecur(n);
    }


    public List<TreeNode> generateTreesRecur(int n) {
        if (memo.containsKey(n)) {
            return copyTreeList(memo.get(n));
        }

        List<TreeNode> res = new ArrayList<>();
        if (n == 0) {
            res.add(null);
            return res;
        }

        if (n == 1) {
            res.add(new TreeNode(1));
            return res;
        }


        for (int i = 1; i <= n; i++) {
            // index i as root
            List<TreeNode> leftSide = generateTreesRecur(i - 1);
            List<TreeNode> rightSide = addTreeValue(generateTreesRecur(n - i), i);

            for (TreeNode left : leftSide) {
                for (TreeNode right : rightSide) {
                    TreeNode root = new TreeNode(i);
                    root.left = copyTree(left);
                    root.right = copyTree(right);
                    res.add(root);
                }
            }
        }

        memo.put(n, copyTreeList(res));
        return res;
    }


    public List<TreeNode> addTreeValue(List<TreeNode> treeNodeList, int val) {
        for (TreeNode node : treeNodeList) {
            midTravelTreeAndAdd(node, val);
        }

        return treeNodeList;
    }

    public void midTravelTreeAndAdd(TreeNode root, int val) {
        if (root == null) {
            return;
        }

        midTravelTreeAndAdd(root.left, val);
        root.val += val;
        midTravelTreeAndAdd(root.right, val);
    }

    public List<TreeNode> copyTreeList(List<TreeNode> treeNodeList) {
        List<TreeNode> dupTreeNodeList = new ArrayList<>();
        for (TreeNode node : treeNodeList) {
            dupTreeNodeList.add(copyTree(node));

        }

        return dupTreeNodeList;
    }

    public TreeNode copyTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode newRoot = new TreeNode(root.val);
        newRoot.left = copyTree(root.left);
        newRoot.right = copyTree(root.right);
        return newRoot;
    }


    public static void main(String[] args) {
        String test = "abbbbacd";
        LC95 an = new LC95();
        System.out.println(an.generateTrees(5));

//
//        TreeNode root=TreeNode.createTree("2,1,3,null,null,null,4");
//        an.midTravelTreeAndAdd(root,1);

    }
}
